import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Num16_19 {
    //你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。
    // 若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。
    // 编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
    public static void main(String[] args) {
        int[][] nums = new int[][]{
                {0, 2, 1, 0},
                {0, 1, 0, 1},
                {1, 1, 0, 1},
                {0, 1, 0, 1}};
        Num16_19 num16_19 = new Num16_19();
        System.out.println(Arrays.toString(num16_19.pondSizes(nums)));
    }

    public int[] pondSizes(int[][] land) {
        int n = land.length;
        int m = land[0].length;
        ArrayList<Integer> arrayList = new ArrayList();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (land[i][j] == 0) {
                    arrayList.add(dfs(land, i, j));
                }
            }
        }
        int len = arrayList.size();
        int[] arr = new int[len];
        Collections.sort(arrayList);
        int ind = 0;
        for (int num : arrayList) {
            arr[ind++] = num;
        }
        return arr;
    }

    private int dfs(int[][] land, int i, int j) {
        int n = land.length;
        int m = land[0].length;
        if (i < 0 || i >= n || j < 0 || j >= m || land[i][j] != 0) return 0;
        int res = 1;
        land[i][j] = -1;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 && dy == 0) {
                    continue;
                }
                res += dfs(land, i + dx, j + dy);
            }
        }
        return res;
    }
}
